package com.dmall.graph.floodfill;

/**
 * @author: xiao1.wang
 * @date: 2022/6/19 20:42
 */
public class Solution785 {

    private int[][] graph;
    private int[] colors;
    private boolean bipartite = true;

    public boolean isBipartite(int[][] graph) {
        this.graph = graph;
        int V = graph.length;
        colors = new int[V];
        for (int i = 0; i < V; i++) {
            if (colors[i] == 0) {
                if (!dfs(i, 1)) {
                    bipartite = false;
                    break;
                }
            }
        }
        return bipartite;
    }

    private boolean dfs(int v, int color) {
        colors[v] = color;
        for (int w : graph[v]) {
            if (colors[w] == 0) {
                if (!dfs(w, 3 - color)) {
                    return false;
                }
            } else {
                if (colors[v] == colors[w]) {
                    return false;
                }
            }
        }
        return true;
    }
}
